#include <bits/stdc++.h>

using namespace std;

// 将数组和减半的最少操作次数
// 测试链接 : https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/

// 使用标准库的堆
class Solution 
{
public:
    int halveArray(vector<int>& nums) 
    {
        // 大根堆
        priority_queue<double> heap;
        double sum = 0;
        for(int num : nums)
        {
            heap.push((double)num);
            sum += num;
        }

        // sum，整体累加和，-> 要减少的目标！
        sum /= 2;
        int ans = 0;
        for(double minus = 0, cur; minus < sum; ++ans, minus += cur)
        {
            cur = heap.top() / 2;
            heap.pop();
            heap.push(cur);
        }
        return ans;
    }
};


// 使用自己写的堆
class Solution 
{
private:
    static const int MAXN = 100001;
    long heap[MAXN];
    int sz;

    void heapify(int i)
    {
        int l = 2 * i + 1;
        while(l < sz)
        {
            int best = l + 1 < sz && heap[l + 1] > heap[l] ? l + 1 : l;
            best = heap[best] > heap[i] ? best : i;
            if(best == i) break;
            swap(heap[best], heap[i]);
            i = best;
            l = 2 * i + 1;
        }
    }

public:
    int halveArray(vector<int>& nums) 
    {
        sz = nums.size();
        long sum = 0;
        // 建堆时间复杂度为 O(N)
        for(int i = sz - 1; i >= 0; --i)
        {
            heap[i] = (long)nums[i] << 20;
            sum += heap[i];
            heapify(i);
        }

        sum /= 2;
        int ans = 0;
        for(long minus = 0; minus < sum; ++ans)
        {
            heap[0] /= 2;
            minus += heap[0];
            heapify(0);
        }
        return ans;
    }
};